package org.dse.web;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * Pagerank is an algorithm that Google utilizes to rank its search results in
 * presence of multiple resources matching a certain query. In very simple words
 * Pagerank evaluates and ranks Web sites according to a computed value
 * determined by the number of other sites linking to them. The way the Pagerank
 * value is computed makes Pagerank somewhat immune to artificial linking
 * efforts.
 * 
 * The rank (a numerical measure of importance) of each web page is dependent on
 * the importance conferred on it by other web pages that have links to it; each
 * web page divides its importance equally amongst all of the web pages it
 * references. The rank R(p) for any web page p can be expressed via a simple
 * summation given the set of web pages B(p) that link to p and the outdegree
 * function d+: V -> Z:
 * 
 * R(p) = sum(q in B(p), R(q)/d+(q))
 * 
 * Note that the right-hand side of the expression may contain R(p), because the
 * rank of some R(q) may depend on R(p). For this reason, the rank of each web
 * page is not computed directly, but instead an iterative algorithm is applied
 * using the formula:
 * 
 * Ri+1(p) = sum(q in B(p), Ri(q)/d+(q))
 * 
 * @author zhangchen
 * 
 */
public class PageRank {

	/** The value for the PageRank dampening factor */
	private double dampening = 0.85;

	/** The data structure containing the Web linkage graph */
	private WebGraph graph;

	/** A <code>Map</code> containing the PageRank values for each page */
	private Map<String, Double> scores;

	/**
	 * Constructor for PageRank.
	 * 
	 * @param graph
	 *            The data structure containing the Web linkage graph
	 */
	public PageRank(WebGraph graph) {
		this.graph = graph;
		this.scores = new HashMap<String, Double>();
		Set<String> linkUrls = graph.availableLink();
		
		int n = graph.numNodes();
		double init = 1.0 / n;

		for (String url : linkUrls) {
			scores.put(url, init);
		}

		computePagerank();
	}

	/**
	 * Set the value for the PageRank dampening factor. The amount of PageRank
	 * that is transferred depends on a dampening factor which stands for the
	 * probability that a random surfer will get bored. The dampening factor
	 * generally is set to 0.85.
	 * 
	 * @param damp
	 *            The dampening factor
	 */
	public void setDampening(double damp) {
		this.dampening = damp;
	}

	/**
	 * Return the dampening factor used for the PageRank Algorithm. The amount
	 * of PageRank that is transferred depends on a dampening factor which
	 * stands for the probability that a random surfer will get bored. The
	 * dampening factor generally is set to 0.85.
	 * 
	 * @return The dampening factor
	 */
	public double getDampening() {
		return this.dampening;
	}

	/**
	 * Returns the PageRank value associated with a given link
	 * 
	 * @param link
	 *            The url for the link
	 * @return The PageRank value associated with the given link
	 */
	public double pageRank(String link) {
		Double score = scores.get(link);
		if (score != null)
			return score.doubleValue();
		else
			return 0;
	}

	/**
	 * Returns the PageRank value map associated with the whole web graph
	 * 
	 * @return The PageRank value map associated with the whole web graph
	 */
	public Map<String, Double> pageRank() {
		return scores;
	}

	/**
	 * Initializes the PageRank value associated with a given link.
	 * 
	 * @param link
	 *            The url for the link
	 * @param value
	 *            The PageRank value to assign
	 */
	public void initializePageRank(String link, double value) {
		scores.put(link, value);
	}

	/**
	 * Computes the PageRank value for all the nodes in the Web Graph. In this
	 * method, the maximum number of iterations of the algorithm is set to 100.
	 * 
	 */
	public void computePagerank() {
		computePagerank(100);
	}

	/**
	 * Computes the PageRank value for all the nodes in the Web Graph. The
	 * formula of Sergey Brin and Lawrence Page (founders of Google) can be
	 * found in their <a
	 * href="http://www-db.stanford.edu/~backrub/google.html">original document</a>.
	 * Essentially:
	 * 
	 * The amount of PageRank that is transferred depends on a dampening factor
	 * which stands for the probability that a random surfer will get bored. The
	 * dampening factor generally is set to 0.85.
	 * 
	 * The more outgoing links a web page has, the less PageRank of that page
	 * will be transferred to each of the pages it links to. Very simple: devide
	 * the real PageRank by the number of outgoing links and multiply it with
	 * the dampening factor to calculate the amount of PageRank that is
	 * transferred.
	 * 
	 * Do this for all pages that link to your page and you know your own
	 * PageRank.
	 * 
	 * @param iter
	 *            The number of iterations for the algorithm
	 * 
	 */
	public void computePagerank(int iter) {
		int n = graph.numNodes();
		double aux = (1 - dampening) / n;
		Set<String> linkUrls = graph.availableLink();
		
		boolean change = true;
		while ((iter--) > 0 && change) {
			change = false;
			Map<String, Double> tempScore = new HashMap<String, Double>();
			for (String url : linkUrls) {
				Set<String> fromPages = graph.inLinks(url);

				double rank = 0;

				for (String fromPage : fromPages) {// for all from pages, its
													// score is divided by its
													// out links number
					Set<String> toPages = graph.outLinks(fromPage);
					int numLink = toPages.size();

					rank = rank + scores.get(fromPage) / numLink;
				}
				rank = aux + dampening * rank;
				tempScore.put(url.intern(), rank);

				if (Math.abs(rank - scores.get(url.intern()).doubleValue()) > 0.00000001)
					change = true;
			}

			for (String url : linkUrls) {
				scores.put(url.intern(), tempScore.get(url.intern()));
			}
		}
	}
}
